package com.fzkj.search;

/**
 * 插值查找
 * @author yaya
 */
public class InterpolationSearch {
    public static void main(String[] args) {
        int[] arr = {1,2,3,6,32,34,122,632,711,988,1000,2233,4564,12345,12346,12347,13245};
        System.out.println(interpolationSearch(arr, 13245));
    }

    /**
     * 查找元素下标
     */
    private static int interpolationSearch(int[] arr, int des){
        int low = 0, high = arr.length - 1;
        while (low <= high){
            int mid = low + ((des - arr[low]) / (arr[high] - arr[low])) * (high - low);
            if (mid < 0 || mid > arr.length - 1) break;
            if (des == arr[mid]){
                return mid;
            } else if (des > arr[mid]) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
